package com.lims.algorithm.algset.graph;

import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * <描述:>
 *
 * @author lims
 * @date 2020-08-26 23:24
 */
public class UDGraphList<T> {
    /**
     * 顶点类
     */
    class VertexNode {
        // 数据
        T data;
        // 第一条边
        EdgeNode firstEdge;
        // 入度
        int inDegree;
        // 出度
        int outDegree;

        public VertexNode(T data, EdgeNode firstEdge) {
            this.data = data;
            this.firstEdge = firstEdge;
        }

        // 入度加1
        public void incrInDegree() {
            inDegree++;
        }

        // 出度加1
        public void incrOutDegree() {
            outDegree++;
        }

        // 入度减1
        public void decrInDegree() {
            inDegree--;
        }

        // 出度减1
        public void decrOutDegree() {
            outDegree--;
        }
    }

    /**
     * 边 类
     */
    class EdgeNode {
        // 指向的结点
        int pVex;
        // 下一条边
        EdgeNode nextEdge;
        // 边权重
        int weight;

        public EdgeNode(int pVex, EdgeNode nextEdge, int weight) {
            this.pVex = pVex;
            this.nextEdge = nextEdge;
            this.weight = weight;
        }
    }

    /**
     * 顶点集合
     */
    List<VertexNode> vertexs;
    /**
     * 访问标记
     */
    boolean[] isVisited;

    public UDGraphList(int n) {
        vertexs = new ArrayList<>(n);
        isVisited = new boolean[n];
    }

    /**
     * 添加顶点
     *
     * @param ver
     */
    public void addListVer(T ver) {
        VertexNode vertexNode = new VertexNode(ver, null);
        vertexs.add(vertexNode);
    }

    /**
     * 添加边
     *
     * @param v1
     * @param v2
     * @param weight
     */
    public void addUnDirectEdge(int v1, int v2, int weight) {
        // 指向V2的边
        EdgeNode e1 = new EdgeNode(v1, null, weight);
        EdgeNode e2 = new EdgeNode(v2, null, weight);

        // v1 - v2边
        if (vertexs.get(v1).firstEdge == null) {
            vertexs.get(v1).firstEdge = e2;
        } else {
            linkEdge(vertexs.get(v1).firstEdge, e2);
        }
        // v1 - v2边
        if (vertexs.get(v2).firstEdge == null) {
            vertexs.get(v2).firstEdge = e1;
        } else {
            linkEdge(vertexs.get(v2).firstEdge, e1);
        }
    }

    public void addDirectEdge(int v1, int v2, int weight){
        EdgeNode v1_2 = new EdgeNode(v2, null, weight);
        VertexNode vertex = vertexs.get(v1);
        if (vertex.firstEdge == null) {
            vertex.firstEdge = v1_2;
        } else {
            EdgeNode firstEdge = vertex.firstEdge;
            do {
                if (firstEdge.nextEdge == null) {
                    firstEdge.nextEdge = v1_2;
                    break;
                }
            } while ((firstEdge = firstEdge.nextEdge) != null);
        }

        vertexs.get(v1).incrOutDegree();
        vertexs.get(v2).incrOutDegree();
    }

    private void linkEdge(EdgeNode firstEdge, EdgeNode edgeNode2) {
        if (firstEdge.nextEdge == null) {
            firstEdge.nextEdge = edgeNode2;
            return;
        }
        linkEdge(firstEdge.nextEdge, edgeNode2);
    }

    /**
     * 返回值
     *
     * @param index
     * @return
     */
    public T getValue(int index) {
        return vertexs.get(index).data;
    }

    /**
     * 显示邻接表
     */
    public void show() {
        System.out.println("邻接表显示：");
        for (int i = 0; i < vertexs.size(); i++) {
            //System.out.printf("%d(%c)", i, verNodeList.get(i).data);
            System.out.print(i + "(" + vertexs.get(i).data + "):");
            EdgeNode firstEdge = vertexs.get(i).firstEdge;
            while (firstEdge != null) {
                System.out.print(firstEdge.pVex + "(" + vertexs.get(firstEdge.pVex).data + ")");
                firstEdge = firstEdge.nextEdge;
            }
            System.out.printf("\n");
        }
    }

    /**
     * 拿到第一个邻接结点
     *
     * @param v1 本节点
     * @return
     */
    public int getFirstAjcNode(int v1) {
        VertexNode verNode = vertexs.get(v1);
        return verNode.firstEdge == null ? -1 : verNode.firstEdge.pVex;
    }

    /**
     * 拿到除去当前节点的下一个邻接结点
     *
     * @param v1 本节点
     * @param v2 已经访问过的结点
     * @return
     */
    public int getNextAjcNode(int v1, int v2) {
        VertexNode verNode = vertexs.get(v1);
        EdgeNode firstEdge = verNode.firstEdge;
        while (firstEdge != null) {
            if (firstEdge.pVex == v2) {
                return firstEdge.nextEdge == null ? -1 : firstEdge.nextEdge.pVex;
            }
            firstEdge = firstEdge.nextEdge;
        }
        return -1;
    }

    /**
     * v1下一个未被访问过的邻接点
     *
     * @param v1
     * @return
     */
    public int getNextListAjcVerNoAccess(int v1) {
        VertexNode verNode = vertexs.get(v1);
        EdgeNode edgeNode = verNode.firstEdge;
        while (edgeNode != null) {
            if (!isVisited[edgeNode.pVex]) {
                return edgeNode.pVex;
            }
            edgeNode = edgeNode.nextEdge;
        }
        return -1;
    }

    /**
     * 清空访问记录
     */
    public void clearVisited() {
        isVisited = new boolean[vertexs.size()];
    }

    /**
     * 深度优先遍历
     */
    public void DFS() {
        System.out.println("深度优先遍历：");
        for (int i = 0; i < vertexs.size(); i++) {
            if (!isVisited[i]) {
                DFS(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    private void DFS(boolean[] isVisited, int i) {
        System.out.print(getValue(i));
        isVisited[i] = true;
        int ajc = getNextListAjcVerNoAccess(i);
        while (ajc != -1) {
            if (!isVisited[ajc]) {
                System.out.print("->");
                DFS(isVisited, ajc);
            }
            ajc = getNextListAjcVerNoAccess(i);
        }
    }

    /**
     * 广度优先遍历
     */
    public void BFS() {
        System.out.println("广度优先遍历：");
        for (int i = 0; i < vertexs.size(); i++) {
            if (!isVisited[i]) {
                BFS(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    private void BFS(boolean[] isVisited, int i) {
        int h;
        int ajc;
        Deque<Integer> queue = new LinkedBlockingDeque<>();
        System.out.print(getValue(i));
        isVisited[i] = true;
        queue.offerLast(i);
        while (!queue.isEmpty()) {
            h = queue.pollFirst();
            ajc = getNextListAjcVerNoAccess(h);
            while (ajc != -1) {
                if (!isVisited[ajc]) {
                    System.out.print("->");
                    System.out.print(getValue(ajc));
                    isVisited[ajc] = true;
                    queue.offerLast(ajc);
                }
                ajc = getNextListAjcVerNoAccess(h);
            }
        }
    }



    /******************************************************/
    public static void main(String[] args) {
        // 节点个数
        int n = 10;
        String[] vertexString = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"};
        UDGraphList<String> udg = new UDGraphList(n);
        // 向图对象添加节点
        for (String s : vertexString) {
            udg.addListVer(s);
        }

        // 添加边AB AC AD AE BC BD CE DE DF DG EH EI IJ
        udg.addUnDirectEdge(0, 1, 1);
        udg.addUnDirectEdge(0, 2, 1);
        udg.addUnDirectEdge(0, 3, 1);
        udg.addUnDirectEdge(0, 4, 1);
        udg.addUnDirectEdge(1, 2, 1);
        udg.addUnDirectEdge(1, 3, 1);
        udg.addUnDirectEdge(2, 4, 1);
        udg.addUnDirectEdge(3, 4, 1);
        udg.addUnDirectEdge(3, 5, 1);
        udg.addUnDirectEdge(3, 6, 1);
        udg.addUnDirectEdge(4, 7, 1);
        udg.addUnDirectEdge(4, 8, 1);
        udg.addUnDirectEdge(8, 9, 1);

        udg.show();

        udg.DFS();
        udg.clearVisited();
        udg.BFS();
    }
}













